/**
 * Description: 两数之和
 * File: 001.cpp |Time: 2022-10-24 10:49
 */
#include <iostream>
#include <vector>
#include <map>

using namespace std;

class Solution {
public:
    // 方法一: 遍历所有, 时间复杂度O(n^2)
    vector<int>twoSum(vector<int> &nums, int target) {
        int i,j;
        for(i = 0; i < nums.size(); i++) {
            for (j = 0; j < nums.size(); j++) 
            {
                if(nums[i] + nums[j] == target){
                    cout << nums[i] << " + " << nums[j] << " = " << target << endl;
                    return {i, j};
                }
            }
        }
    }


    // 方法二: 借用哈希表的键值对存储形式, 通过查找键来获得有效索引, 时间复杂度O(1)
    vector<int>twoSumMap(vector<int> &nums, int target) {
        map<int, int> num_map;
        map<int, int>::iterator it;
        for (int i = 0; i < nums.size(); i++) {
            it = num_map.find(target - nums[i]);
            if(it != num_map.end()){
                cout << nums[it->second] << " + " << nums[i] << " = " << target << endl;
                return {it->second, i};
            }
            num_map[nums[i]] = i;
        }
    }
    
};

int main(int argc, const char *argv[])
{
    
    vector<int> nums{1, 23, 14, 15};
    Solution *s = new Solution;
    s->twoSum(nums, 15);
    s->twoSumMap(nums, 15);
    return 0;
}


